package org.liaohailong.helloworld.hash;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * Author: liaohailong
 * Date: 2021/5/22
 * Time: 9:27
 * Description:
 **/
public class HashSolution {
//    public boolean containsDuplicate(int[] nums) {
//        HashSet<Integer> hashSet = new HashSet<>();
//        for (int num : nums) {
//            if (hashSet.contains(num)) {
//                return true;
//            }
//            hashSet.add(num);
//        }
//        return false;
//    }


    public int singleNumber(int[] nums) {
        int a = nums[0];
        for (int i = 1; i < nums.length; i++) {
            a ^= nums[i];
        }
        return a;
    }

    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> hash = new HashSet<>();
        HashSet<Integer> res = new HashSet<>();
        for (int value : nums1) {
            hash.add(value);
        }
        for (int value : nums2) {
            if (hash.contains(value)) {
                res.add(value);
            }
        }
        int[] same = new int[res.size()];
        int pos = -1;
        for (Integer val : res) {
            pos++;
            same[pos] = val;
        }
        return same;
    }

    // LC 快乐数
//    public boolean isHappy(int n) {
//        return isHappy(n, new HashSet<>());
//    }
//
//    public boolean isHappy(int n, HashSet<Integer> record) {
//        if (record.contains(n)) return false;
//        record.add(n);
//
//        LinkedList<Integer> nums = new LinkedList<>();
//        while (n > 0) {
//            int one = n % 10;
//            nums.addFirst(one);
//            n /= 10;
//        }
//        int res = 0;
//        for (Integer val : nums) {
//            res += (val * val);
//        }
//        if (res == 1) return true;
//        else {
//            return isHappy(res, record);
//        }
//    }

    // LC 快乐数 - 快慢指针
    public boolean isHappy(int n) {
        int slow = n;
        int fast = n;

        while (true) {
            slow = cal(slow);
            fast = cal(fast);
            fast = cal(fast);
            if (slow == 1 || fast == 1) return true;
            if (slow == fast) return false;
        }
    }

    private int cal(int n) {
        int res = 0;
        while (n > 0) {
            res += (int) Math.pow(n % 10, 2);
            n /= 10;
        }
        return res;
    }


    // LC 同构字符串
    public boolean isIsomorphic(String s, String t) {
        HashMap<Character, Integer> cache1 = new HashMap<>();
        HashMap<Character, Integer> cache2 = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);

            Integer index1 = cache1.get(c1);
            Integer index2 = cache2.get(c2);

            if (index1 == null && index2 == null) {
                cache1.put(c1, i);
                cache2.put(c2, i);
                continue;
            }

            if (index1 == null || index2 == null) return false;

            if (!index1.equals(index2)) return false;

            cache1.put(c1, i);
            cache2.put(c2, i);
        }

        return true;
    }

    // LC 两个列表的最小索引总和
//    public String[] findRestaurant(String[] list1, String[] list2) {
//        HashMap<String, Integer> map1 = new HashMap<>();
//        for (int i = 0; i < list1.length; i++) {
//            map1.put(list1[i], i);
//        }
//
//        HashMap<String, Integer> map2 = new HashMap<>();
//        int min = Integer.MAX_VALUE;
//        for (int i = 0; i < list2.length; i++) {
//            Integer index1 = map1.get(list2[i]);
//            if (index1 != null) {
//                int offset = i + index1;
//                if (offset < min) min = offset;
//                map2.put(list2[i], offset);
//            }
//        }
//
//        LinkedList<String> res = new LinkedList<>();
//        for (Map.Entry<String, Integer> entry : map2.entrySet()) {
//            String name = entry.getKey();
//            Integer offset = entry.getValue();
//            if (offset > min) continue;
//            res.addLast(name);
//        }
//
//        String[] result = new String[res.size()];
//        int pos = -1;
//        for (String s : res) {
//            pos++;
//            result[pos] = s;
//        }
//        return result;
//    }


    // LC 两个列表的最小索引总和
    public String[] findRestaurant(String[] list1, String[] list2) {
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < list1.length; i++) {
            map.put(list1[i], i);
        }

        LinkedList<String> result = new LinkedList<>();
        int min = Integer.MAX_VALUE;
        int sum;
        for (int j = 0; j < list2.length && j <= min; j++) {
            if (map.containsKey(list2[j])) {
                sum = j + map.get(list2[j]);
                if (sum < min) {
                    result.clear();
                    result.add(list2[j]);
                    min = sum;
                } else if (sum == min) {
                    result.add(list2[j]);
                }
            }
        }
        String[] res = new String[result.size()];
        int pos = -1;
        for (String s : result) {
            pos++;
            res[pos] = s;
        }
        return res;
    }

//    // LC 字符串中的第一个唯一字符
//    public int firstUniqChar(String s) {
//        HashMap<Character, Integer> hashMap = new HashMap<>();
//        LinkedList<Integer> indexList = new LinkedList<>();
//        for (int i = 0; i < s.length(); i++) {
//            char c = s.charAt(i);
//            if (hashMap.containsKey(c)) {
//                Integer index = hashMap.get(c);
//                indexList.remove(index);
//                hashMap.put(c, i);
//            } else {
//                hashMap.put(c, i);
//                indexList.addLast(i);
//            }
//        }
//        return indexList.isEmpty() ? -1 : indexList.peekFirst();
//    }

    // LC 字符串中的第一个唯一字符
    public int firstUniqChar(String s) {
        LinkedHashMap<Character, Pair<Integer, Boolean>> hashMap = new LinkedHashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (hashMap.containsKey(c)) {
                hashMap.get(c).second = false;
            } else {
                hashMap.put(c, new Pair<>(i, true));
            }
        }
        for (Map.Entry<Character, Pair<Integer, Boolean>> entry : hashMap.entrySet()) {
            Pair<Integer, Boolean> value = entry.getValue();
            if (value.second) return value.first;
        }
        return -1;
    }

    private static final class Pair<F, S> {
        F first;
        S second;

        public Pair(F first, S second) {
            this.first = first;
            this.second = second;
        }
    }

    // 两个数组的交集 II
//    public int[] intersect(int[] nums1, int[] nums2) {
//        LinkedHashMap<Integer, Integer> hashMap1 = new LinkedHashMap<>();
//        for (int i : nums1) {
//            if (hashMap1.containsKey(i)) {
//                Integer count = hashMap1.get(i);
//                count++;
//                hashMap1.put(i, count);
//            } else hashMap1.put(i, 1);
//        }
//
//        LinkedHashMap<Integer, Integer> hashMap2 = new LinkedHashMap<>();
//        for (int i : nums2) {
//            if (hashMap2.containsKey(i)) {
//                Integer count = hashMap2.get(i);
//                count++;
//                hashMap2.put(i, count);
//            } else hashMap2.put(i, 1);
//        }
//
//        LinkedList<Integer> res = new LinkedList<>();
//        for (Map.Entry<Integer, Integer> entry : hashMap1.entrySet()) {
//            Integer key = entry.getKey();
//            if (hashMap2.containsKey(key)) {
//                Integer count2 = hashMap2.get(key);
//                Integer count1 = entry.getValue();
//                int count = Math.min(count1, count2);
//                for (int i = 0; i < count; i++) {
//                    res.add(key);
//                }
//            }
//        }
//
//        int[] result = new int[res.size()];
//        int pos = -1;
//        for (Integer val : res) {
//            pos++;
//            result[pos] = val;
//        }
//        return result;
//    }


    // 两个数组的交集 II - 快排
    public int[] intersect(int[] nums1, int[] nums2) {
        // 快排两个数组
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        // 找到交集起点
        int index1 = -1;
        int index2 = -1;
        if (nums1[0] > nums2[0]) {
            index1 = 0;
            for (int i = 0; i < nums2.length; i++) {
                if (nums2[i] >= nums1[0]) {
                    index2 = i;
                    break;
                }
            }
        } else if (nums1[0] < nums2[0]) {
            index2 = 0;
            for (int i = 0; i < nums1.length; i++) {
                if (nums1[i] >= nums2[0]) {
                    index1 = i;
                    break;
                }
            }
        } else {
            index1 = 0;
            index2 = 0;
        }


        LinkedList<Integer> list = new LinkedList<>();
        int[] res = new int[]{0, 0};
        while (index1 < nums1.length && index2 < nums2.length) {
            if (nums1[index1] == nums2[index2]) {
                // 找到相同元素
                int val = nums1[index1];

                // 计算最小出现次数
                res[0] = 0;
                res[1] = 0;
                findCount(nums1, index1, res);
                index1 = res[0] + 1;
                int count1 = res[1];

                res[0] = 0;
                res[1] = 0;

                findCount(nums2, index2, res);
                index2 = res[0] + 1;
                int count2 = res[1];

                int min = Math.min(count1, count2);
                for (int i = 0; i < min; i++) {
                    list.add(val);
                }
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else if (nums1[index1] < nums2[index2]) {
                index1++;
            }
        }

        int[] result = new int[list.size()];
        int pos = -1;
        for (Integer integer : list) {
            pos++;
            result[pos] = integer;
        }

        return result;
    }

    private void findCount(int[] arr, int beginIndex, int[] res) {
        int val = arr[beginIndex];
        res[0] = beginIndex;
        res[1]++;
        for (int i = beginIndex + 1; i < arr.length; i++) {
            if (arr[i] == val) {
                res[0] = i;
                res[1]++;
            } else break;
        }
    }

    // LC 存在重复元素 II
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (hashMap.containsKey(nums[i])) {
                if (i - hashMap.get(nums[i]) <= k) return true;
                else hashMap.put(nums[i], i);
            } else {
                hashMap.put(nums[i], i);
            }
        }
        return false;
    }

    // LC 宝石与石头
    public int numJewelsInStones(String jewels, String stones) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < jewels.length(); i++) {
            char c = jewels.charAt(i);
            hashMap.put(c, 0);
        }

        int total = 0;
        for (int i = 0; i < stones.length(); i++) {
            char c = stones.charAt(i);
            if (hashMap.containsKey(c)) {
                total++;
            }
        }

        return total;
    }

    //    执行用时：
//            9 ms
//, 在所有 Java 提交中击败了
//39.98%
//    的用户
//    内存消耗：
//            39 MB
//, 在所有 Java 提交中击败了
//15.74%
//    的用户
    // LC 无重复字符的最长子串
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        Character[] arr = new Character[s.length()];
        int maxCount = 0;
        int count = 0;
        int from = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (hashMap.containsKey(c)) {
                if (maxCount < count) maxCount = count;
                int to = hashMap.remove(c);
                remove(hashMap, arr, from, to);
                from = to;
                count = i - to;
                hashMap.put(c, i);
                arr[i] = c;
            } else {
                hashMap.put(c, i);
                count++;
                arr[i] = c;
            }
        }
        if (maxCount < count) maxCount = count;
        return maxCount;
    }

    private void remove(HashMap<Character, Integer> hashMap,
                        Character[] arr,
                        int from, int to) {
        for (int i = from; i <= to; i++) {
            Character character = arr[i];
            if (character == null) continue;
            hashMap.remove(character);
            arr[i] = null;
        }
    }

    // LC 四数相加 II 参数数组长度都是一致的
//    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
//        int[][] total = new int[4][nums1.length];
//        total[0] = nums1;
//        total[1] = nums2;
//        total[2] = nums3;
//        total[3] = nums4;
//
//        int[] res = new int[]{0};
//        int[] path = new int[4];
//        for (int i = 0; i < total[0].length; i++) {
//            _fourSumCount(total, 0, i, path, res);
//        }
//
//        return res[0];
//    }

//    private void _fourSumCount(int[][] total, int depth, int index, int[] path, int[] res) {
//        int[] nums = total[depth];
//        path[depth] = nums[index];
//
//        depth++;
//        if (depth >= total.length) {
//            // 计算结果
//            int result = 0;
//            for (int value : path) {
//                result += value;
//            }
//            if (result == 0) res[0]++;
//            return;
//        }
//        for (int i = 0; i < total[depth].length; i++) {
//            _fourSumCount(total, depth, i, path, res);
//        }
//    }


    // LC 四数相加 II 参数数组长度都是一致的
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer, Integer> hashMap1 = new HashMap<>();
        HashMap<Integer, Integer> hashMap2 = new HashMap<>();

        for (int item : nums1) {
            for (int value : nums2) {
                int res = item + value;
                hashMap1.put(res, hashMap1.getOrDefault(res, 0) + 1);
            }
        }

        for (int item : nums3) {
            for (int value : nums4) {
                int res = item + value;
                hashMap2.put(res, hashMap2.getOrDefault(res, 0) + 1);
            }
        }

        int result = 0;
        for (Map.Entry<Integer, Integer> entry : hashMap1.entrySet()) {
            Integer key = entry.getKey();
            Integer value = entry.getValue();

            Integer count = hashMap2.get(-key);
            if (count != null) result += (count * value);
        }


        return result;
    }

    // LC 前 K 个高频元素
    public int[] topKFrequent(int[] nums, int k) {

        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int val : nums) {
            hashMap.put(val, hashMap.getOrDefault(val, 0) + 1);
        }
        Entry[] entries = new Entry[hashMap.size()];

        Iterator<Map.Entry<Integer, Integer>> iterator = hashMap.entrySet().iterator();
        int pos = 0;
        while (iterator.hasNext()) {
            Map.Entry<Integer, Integer> next = iterator.next();
            entries[pos] = new Entry(next.getKey(), next.getValue());
            pos++;
        }

        Arrays.sort(entries);

        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = entries[i].val;
        }

        return result;
    }

    private static final class Entry implements Comparable<Entry> {
        int val;
        int count;

        public Entry(int val, int count) {
            this.val = val;
            this.count = count;
        }

        @Override
        public int compareTo(Entry o) {
            return Integer.compare(o.count, count);
        }
    }
}
